#include<algorithm>
using std::max;


struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxSum = root->val;
        recordBestPath(root, maxSum);
        return maxSum;
    }

    int recordBestPath(TreeNode* root, int& maxSum) {
        if (root == nullptr) return 0;
        int leftSum = recordBestPath(root->left, maxSum);
        int rightSum = recordBestPath(root->right, maxSum);
        leftSum = max(0, leftSum);
        rightSum = max(0, rightSum);
        int currentSum = root->val + max(leftSum, rightSum);    //记录包含当前root节点的最大和(不同时包含两个子树，避免路径重复)
        maxSum = max(maxSum, root->val+leftSum+rightSum);
        return currentSum;

    }
};